﻿using System;
using System.Collections.Generic;

namespace Component.Tools
{
    public class PriorityQueue<T>
    {
        private IComparer<T> comparer;
        private T[] heap;
        
        public int Count { get; private set; }
        
        public PriorityQueue() : this(null) { }
        public PriorityQueue(int capacity) : this(capacity, null) { }
        public PriorityQueue(IComparer<T> comparer) : this(16, comparer) { }

        public PriorityQueue(int capacity, IComparer<T> c)
        {
            comparer = c;
            heap = new T[capacity];
        }

        public void Push(T v)
        {
            if (Count >= heap.Length)
            {
                Array.Resize(ref heap, Count * 2);
            }

            heap[Count] = v;
            SortUp(Count++);
        }
        
        public T Pop()
        {
            var v = Peek();
            heap[0] = heap[--Count];
            if (Count > 0)
            {
                SortDown(0);
            }

            return v;
        }

        private T Peek()
        {
            if (Count > 0)
            {
                return heap[0];
            }
            throw new InvalidOperationException("priorityQueue is empty");
        }

        /// <summary>
        /// 一般从最后一个上浮到合适位置
        /// </summary>
        /// <param name="i">操作位置</param>
        private void SortUp(int i)
        {
            var v = heap[i];
            for (var i2 = i / 2; i > 0 && comparer.Compare(v, heap[i2]) > 0; i = i2, i2 /= 2)
            {
                heap[i] = heap[i2];
            }
            heap[i] = v;
        }
        /// <summary>
        /// 一般从最顶上往下找合适的位置
        /// </summary>
        /// <param name="i">操作位置</param>
        private void SortDown(int i)
        {
            var v = heap[i];
            for (int child = i*2; child < Count; i = child, child *= i)
            {
                if (child + 1 < Count && comparer.Compare(heap[child + 1], heap[child]) > 0)
                {
                    child++;
                }
                if(comparer.Compare(v, heap[child]) > 0) break;
                heap[i] = heap[child];
            }

            heap[i] = v;
        }
    }
}